package outrasolucao;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class Grafo implements Cloneable {
	
	private Map<Object, Vertice> vertices = new HashMap();
	
	
	public void addVertice(Object valor) {
		vertices.put(valor, new Vertice(valor));
	}
	
	public void addAresta(Object verticeOrigem, Object verticeDestino, Custo custo) {
		Vertice origem = vertices.get(verticeOrigem);
		Vertice destino = vertices.get(verticeDestino);
		origem.addAresta(destino, custo);
	}
	
	
	public Collection <Vertice> getVertices() {
		return vertices.values();
	}
	
	
	public Double L(Object verticeOrigem, Object verticeDestino) {
		
		Vertice origem = vertices.get(verticeOrigem);
		Vertice destino = vertices.get(verticeDestino);
		
		return L(origem, destino);
	}
	
	public Double L(Vertice origem, Vertice destino) {
		
		Aresta aresta = origem.getAresta(destino);
		
		if (aresta == null) {
			return Double.POSITIVE_INFINITY;
		} else if (origem.equals(destino)) {
			return new Double(0);
		} else {
			return (Double) aresta.getCusto().getValor();
		} 
	}
	
	
	
	
	public static Map<Object, Double> djikitra(Grafo g, Object verticeOrigem) {
		try {
			
			Map<Object, Double> distancias = new HashMap<>();
			Grafo grafo = (Grafo) g.clone();
			
			Collection<Object> vertices =  grafo.vertices.keySet();

			
			Collection<Object> s = new ArrayList<>();
			vertices.remove(verticeOrigem);
			s.add(verticeOrigem);

			distancias.put(verticeOrigem, new Double(0));
			
			for (Object verticeDestino : vertices) {
				distancias.put(verticeDestino, grafo.L(verticeOrigem, verticeDestino));
			}
			
			while (s.size() != vertices.size()) {
				
				Object verticeMinimo = verticeDistanciaMinima(distancias, vertices);
				s.add(verticeMinimo);
				vertices.remove(verticeMinimo);
				
				for (Object vertice : vertices) {
					Double soma = distancias.get(verticeMinimo) + grafo.L(verticeMinimo, vertice);
					Double menorDistancia = Math.min(distancias.get(vertice), soma);
					distancias.put(vertice, menorDistancia);
					
					if (soma < distancias.get(vertice)) {
						
					}
				}
				
			}
			return distancias;
		} catch (Exception e) {
			e.printStackTrace();
		}
		return null;

		
	}
	
	//encontra o vertice que possui a menor distancia, dentro do array de distancia, 
	//considerando apenas aqueles vertices dentro da coleção 'vertices'
	public static Object verticeDistanciaMinima(Map<Object, Double> distancias, Collection <Object> vertices) {
		
		Double menorDistancia = Double.POSITIVE_INFINITY;
		Object verticeMenorDistancia = null;
		
		for (Object vertice : vertices) {
			if (distancias.get(vertice).compareTo(menorDistancia) < 0) {
				menorDistancia = distancias.get(vertice);
				verticeMenorDistancia = vertice;
			}
		}
		
		return verticeMenorDistancia;
		
	} 

}
